/**
 * <p>Project: </p>
 * <p>File: buddy_pmm.c</p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2016</p>
 * @author 王树根
 * @email: wangshugen@ict.ac.cn
 * @date 2016年6月5日
 */

#include <buddy_pmm.h>
#include <pmm.h>
#include <list.h>
#include <assert.h>
#include <stdio.h>
#include <math.h>

typedef struct Buddy {
	// 伙伴大小(2的次幂)，在头结点表示最大的2的次幂空闲块
	size_t power;
	// 伙伴的可用页面大小(for speed up purpose)，头结点为可用页面数量,也方便比较
	size_t property;
	// 用于组织buddy节点, 和page共享
	list_entry_t node;
} buddy_t, *buddy_ptr_t;

// buddy
buddy_t _buddy;

// 辅助遍历伙伴函数
static void traverse_free_page_list(void);

// 将@base以2为基数进行多次拆分插入伙伴系统
static void _buddy_insert_page(struct Page * base);

// 进行合并
static void _buddy_merge_page(struct Page * ltp, struct Page * gtp, bool lfixed);

// 判断是否为头结点
static inline bool is_buddy_head(list_entry_t * lep) {
	return lep == &(_buddy.node);
}

// 获取首节点
static inline list_entry_t * get_buddy_head(void) {
	return &(_buddy.node);
}

// 获取剩余可用空闲块数量
static inline size_t buddy_nr_free_pages(void) {
	return _buddy.property;
}

static void buddy_init(void) {
	list_init(&(_buddy.node));
	_buddy.property = 0;
	_buddy.power = 0;
}

static void buddy_init_memmap(struct Page *base, size_t n) {
	// 可用空闲块必须大于0
	assert(n > 0);

#ifdef _USE_DEBUG
	cprintf("avialable pages: %d\n", n);
#endif
	// 设置可用空间大小
	struct Page *p = base;
	_buddy.property += n;

	// 指数计数变量
	register volatile int cnt;

	// 进行切分插入
	size_t size;
	struct Page * bp;
	while (n > 0) {
		// 求剩下部分的最大2次幂
		cnt = log2_round_down(n);
		size = pow2(cnt);
		n -= size;

		// 记录最大的2的次幂(初始化时只需要记录一次,后面再进行修改)
		if (_buddy.power == 0) {
			_buddy.power = cnt;
		}

		// 更新空闲块头指针
		bp = p;
		for (; p != bp + size; p++) {
			assert(PageReserved(p));
			p->flags = p->property = 0;
			set_page_ref(p, 0);
		}
		bp->property = size;
		SetPageProperty(bp);

		// 加入头结点后(按从小到大的顺序组织)
		list_add(get_buddy_head(), &(bp->page_link));

		// 拆分完成，跳出
		if (n == 0) {
			break;
		}
	}

#ifdef _USE_DEBUG
	traverse_free_page_list();
#endif
}

static struct Page * buddy_alloc_pages(size_t n) {
	assert(n > 0);
	if (n > buddy_nr_free_pages()) {
		return NULL;
	}

#ifdef _USE_DEBUG
	cprintf("request for %d.\n", n);
#endif
	// 计算对n进行以2为底求对数向上取整计算
	size_t cnt = log2_round_up(n);
	if (cnt > _buddy.power) {
		return NULL;
	}

	n = pow2(cnt);
	struct Page * page = NULL;
	list_entry_t * lep = get_buddy_head();
	while ((lep = list_next(lep)) != get_buddy_head()) {
		page = le2page(lep, page_link);

		// 第一个符合条件的空闲块
		if (page->property >= n) {
			break;
		}
	}

	if (page != NULL) {
		// 取下节点
		list_del(&(page->page_link));
#ifdef _USE_DEBUG
		cprintf("selected with %d.\n", page->property);
#endif
		// 大小不是刚好合适
		if (page->property != n) {
			// 进行多轮拆分和多轮合并
			struct Page * p = page + n;
			p->property = page->property - n;
			page->property = n;

			_buddy_insert_page(p);
		}

		// 更新空闲块数量
		_buddy.property -= n;

		// 更新最大次幂项,  是最大次幂项，且该项无伙伴节点
		if (cnt == _buddy.power && is_buddy_head(list_next(lep))) {
			lep = list_prev(lep);

			// 前一项为头结点
			if (lep == get_buddy_head()) {
				_buddy.power = 0;
			} else {
				_buddy.power = log2(le2page(lep, page_link)->property);
			}
		}
#ifdef _USE_DEBUG
		cprintf("alloc with %d.\n", page->property);
#endif
	}

#ifdef _USE_DEBUG
	traverse_free_page_list();
#endif

	return page;
}

static void buddy_free_pages(struct Page *base, size_t n) {
	assert(n == 0 || base->property == n);

	// if base->property is set properly, n is not used.
	_buddy_insert_page(base);
#ifdef _USE_DEBUG
	cprintf("revoke %d from user.\n", base->property);
	traverse_free_page_list();
#endif
}

void _buddy_insert_page(struct Page * base) {
	size_t n = base->property;
	size_t cnt;
	bool found_flag;
	struct Page * p = base;
	struct Page *ltp, *gtp;
	list_entry_t *prev, *next;

	// TODO 待优化，可以记住当前使用的链表指针，先往后找，然后依次往前找
	while (n > 0) {
		// 进行向下取整分裂
		cnt = log2_round_down(n);
		p->property = pow2(cnt);

		// 更新可用空闲块数量及最大指数幂
		_buddy.property += p->property;
		if (_buddy.power < cnt) {
			_buddy.power = cnt;
		}

		n -= p->property;

		/**
		 * 寻找插入点
		 * 插入点是这样的节点，该page节点(ltp)满足:
		 * 		ltp->propery <= p->property
		 * 同时满足
		 * 		p->property <= gtp->property
		 */
		ltp = NULL;
		gtp = NULL;
		found_flag = false;
		for (prev = get_buddy_head(), next = list_next(prev);
			next != get_buddy_head();
		    prev = next, next = list_next(prev)) {
			// 头节点不能够转换为Page
			ltp = le2page(prev, page_link);
			gtp = le2page(next, page_link);

			// 查找符合要求的节点
			if ((ltp->property <= p->property)
				&& (p->property <= gtp->property)) {
				found_flag = true;
				break;
			}
		}

		// ltp、gtp均为NULL，buddy列表为空
		if (ltp == NULL && gtp == NULL) {
			// 添加在链表头部
			list_add_after(get_buddy_head(), &p->page_link);
		} else {
			if (found_flag) {
				// ltp、gtp均不为NULL，找到了符合要求的节点
				// 进行地址比较
				if (ltp->property == p->property) {
					_buddy_merge_page(ltp, p, true);
				} else if (p->property == gtp->property) {
					_buddy_merge_page(p, gtp, false);
				} else {
					// 直接插入在ltp后、gtp前
					list_add_after(&ltp->page_link, &p->page_link);
				}
			} else {
				// 重新查找
				next = get_buddy_head();
				gtp = NULL;
				while ((next = list_next(next)) != get_buddy_head()) {
					gtp = le2page(next, page_link);
					if (p->property <= gtp->property) {
						break;
					}
				}

				assert(gtp != NULL);
				if (p->property == gtp->property) {
					_buddy_merge_page(p, gtp, false);
				} else if (p->property < gtp->property) {
					list_add_before(&gtp->page_link, &p->page_link);
				} else {
					list_add_after(&gtp->page_link, &p->page_link);
				}
			}
		}

		// 插入完成，跳出循环
		if (n == 0) {
			break;
		}

		// 指针前移
		p += p->property;
	}
}

/**
 * 合并页面，递归合并
 * @lfixed 左边节点为固定节点
 */
void _buddy_merge_page(struct Page * ltp, struct Page * gtp, bool lfixed) {
	assert(ltp->property == gtp->property && ltp != gtp);

	// 地址交换处理
	struct Page *node = lfixed ? ltp : gtp;
	struct Page *p;
	bool swap_flag = ltp > gtp;
	if (swap_flag) {
		p = gtp;
		gtp = ltp;
		ltp = p;
	}

	if ((ltp + ltp->property) != gtp) {
		if (swap_flag) {
			list_add_after(&node->page_link, &ltp->page_link);
		} else {
			list_add_after(&node->page_link, &gtp->page_link);
		}
		return;
	}

	// 摘下节点
	p = ltp;
	p->property *= 2;
	list_del(&node->page_link);

	// 更新最大可用空闲块
	if (log2(p->property) > _buddy.power) {
		_buddy.power = log2(p->property);
	}

	_buddy_insert_page(p);
}

static void
basic_check(void) {
	// 进行次幂计算
	struct Page *p0, *p1, *p2;
	p0 = p1 = p2 = NULL;

	// 最大的buddy空闲块大小
	size_t maxbuddy = pow2(_buddy.power);

	// 申请超过该数量
	assert((p0 = alloc_pages(maxbuddy + 1)) == NULL);

	// 申请最大数量 -1
	assert((p0 = alloc_pages(maxbuddy - 1)) != NULL);
	free_pages(p0, p0->property);

	assert((p1 = alloc_pages(maxbuddy)) != NULL);
	assert(p0 == p1);
	free_pages(p1, p1->property);

#ifdef _USE_DEBUG
	traverse_free_page_list();
#endif
}

static void buddy_check(void) {
	int count = 0, total = 0;
	list_entry_t *lep = &(_buddy.node);
	while ((lep = list_next(lep)) != &(_buddy.node)) {
		struct Page *p = le2page(lep, page_link);
		assert(PageProperty(p));
		count++, total += p->property;
	}
	assert(total == nr_free_pages());

	// 执行基本检查
	basic_check();
}

/**
 * Traverse a free_list.
 * for debug purpose.
 */
void traverse_free_page_list(void) {
	list_entry_t *lep = &(_buddy.node);

	if (list_empty(lep)) {
		cprintf("empty list!!!\n");
		return;
	}

	cprintf("page count: %d, max buddy size: 2^%d = %d\n",
	    _buddy.property, _buddy.power, pow2(_buddy.power));
	struct Page *ptr;
	while ((lep = list_next(lep)) != &(_buddy.node)) {
		ptr = le2page(lep, page_link);

		cprintf(">>> page base: %p, size: 2 ^ %2d = %-8d,  page_ref: %d\n",
		    ptr, log2_round_down(ptr->property), ptr->property, ptr->ref);
	}
}

const struct pmm_manager buddy_pmm_manager = {
    .name = "buddy_pmm_manager",
    .init = buddy_init,
    .init_memmap = buddy_init_memmap,
    .alloc_pages = buddy_alloc_pages,
    .free_pages = buddy_free_pages,
    .nr_free_pages = buddy_nr_free_pages,
    .check = buddy_check,
};
